package com.atguigu.prim;

import java.util.Arrays;

public class PrimAlgorithm {

    public static void main(String[] args) {
        char[] data = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        int verxs = data.length;
        int[][] weight = new int[][] { { 0, 5, 7, 0, 0, 0, 2 }, { 5, 0, 0, 9, 0, 0, 3 }, { 7, 0, 0, 0, 8, 0, 0 },
                { 0, 9, 0, 0, 0, 4, 0 }, { 0, 0, 8, 0, 0, 5, 4 }, { 0, 0, 0, 4, 5, 0, 6 }, { 2, 3, 0, 0, 4, 6, 0 }, };

        MGraph graph = new MGraph(verxs);

        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);
        minTree.showGraph(weight);

        minTree.prim(graph, 1);
    }

}

class MinTree {
    public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
        graph.verxs=verxs;
        for (int i = 0; i < verxs; i++) {
            graph.data[i] = data[i];

            for (int j = 0; j < verxs; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    public void showGraph(int[][] weight) {
        for (int[] item : weight) {
            System.out.println(Arrays.toString(item));
        }
    }

    public void prim(MGraph graph, int v) {

        int[] visited = new int[graph.verxs];
        visited[v]=1;
        int h1=0;
        int h2=0;
        int minWeight = Integer.MAX_VALUE;
        for (int k = 1; k < graph.verxs; k++) {// 从1出发，因为第一个顶点已经被访问，可以少循环一次。三次循环因为是从任意顶点出发
            for (int i = 0; i < graph.verxs; i++) {
                for (int j = 0; j < graph.verxs; j++) {
                    if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight&&graph.weight[i][j]!=0) {
                        minWeight = graph.weight[i][j];
                        h1=i;
                        h2=j;

                    }
                }
            }
            System.out.println("出发" + graph.data[h1] + "," + graph.data[h2] + "> 最小值:" + minWeight);
            visited[h2]=1;
            minWeight=Integer.MAX_VALUE;
        }

     
    }
}

class MGraph {
    int verxs;
    char[] data;
    int[][] weight;

    // 图需要边，需要数据，需要权值
    public MGraph(int verxs) {
        verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}
